import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author shuang
 * @date 2022/5/2 14:23
 * 30. 串联所有单词的子串
 * https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
 */
public class Solutions_30 {
    public static void main(String[] args) {
//        String s = "barfoothefoobarman";
//        String[] words = {"foo", "bar"};  // output: {0, 9}

//        String s = "bbbarfoothefoobarman";
//        String[] words = {"foo", "bar"};  // output: {2, 11}

//        String s = "wordgoodgoodgoodbestword";
//        String[] words = {"word", "good", "best", "word"};  // output: {}

        String s = "goodgoodwordgoodbestword";
        String[] words = {"word", "good", "best", "word"};  // output: {8}

//        String s = "barfoofoobarthefoobarman";
//        String[] words = {"bar", "foo", "the"};  // output: {6, 9, 12}

        Solutions_30 obj = new Solutions_30();
        List<Integer> result = obj.findSubstring(s, words);
        System.out.println(result);
    }

    private List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        // 记录 words 中各单词出现的次数
        Map<String, Integer> wordMap = new HashMap<>();
        for (String word : words) {
            if (!s.contains(word)) {
                // words 中的单词，在字符串 s 中不存在
                return res;
            }
            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
        }
        int strLen = s.length();
        int wordCnt = words.length;
        int wordLen = words[0].length();
        for (int i = 0; i < wordLen; i++) {
            // 定义左右指针
            int left = i, right = i;
            // 窗口中字符串的数量
            int curWordCnt = 0;
            // 窗口中字符串及其出现的次数
            Map<String, Integer> hasWords = new HashMap<>();
            while (right + wordLen <= strLen) {
                String str = s.substring(right, right + wordLen);
                right += wordLen;
                if (wordMap.containsKey(str)) {
                    hasWords.put(str, hasWords.getOrDefault(str, 0) + 1);
                    curWordCnt ++;
                    // 控制窗口中某字符串的数量不能大于 words 中该字符串的数量
                    while (hasWords.get(str) > wordMap.get(str)) {
                        String rmStr = s.substring(left, left + wordLen);
                        // 移动左指针
                        left += wordLen;
                        hasWords.put(rmStr, hasWords.get(rmStr) - 1);
                        curWordCnt --;
                    }
                } else {
                    // 该子串不在 words 中，该窗口失效
                    left = right;
                    hasWords.clear();
                    curWordCnt = 0;
                }
                if (curWordCnt == wordCnt) {
                    res.add(left);
                }
            }
        }
        return res;
    }
}

